package base

import "traning/algorithm/utility"

func NewMyBigHeap(limit int) *MyBigHeap {
	return &MyBigHeap{arr: make([]int, limit), size: 0, limit: limit}
}

type MyBigHeap struct {
	arr []int
	limit int
	size int
}

func (h *MyBigHeap) Push(val int) {
	if h.size == h.limit {panic(any("heap is full !!"))}
	h.arr[h.size] = val
	h.Insert(h.size)
	h.size++
}

func (h *MyBigHeap) Pop() int {
	if h.size == 0 {panic(any("heap is empty !!"))}
	ans := h.arr[0]
	utility.Swap(h.arr, 0, h.size-1)
	h.size--
	h.Heapify(0)
	return ans
}

func (h *MyBigHeap) IsFull() bool {
	return h.size == h.limit
}

func (h *MyBigHeap) IsEmpty() bool {
	return h.size == 0
}

func (h *MyBigHeap)Insert(index int) {
	parent := (index-1)/2
	for h.arr[index] > h.arr[parent] {
		utility.Swap(h.arr, index, parent)
		index = parent
		parent = (index-1)/2
	}
}

func (h *MyBigHeap)Heapify(index int) {
	left := (index<<1) + 1
	var bigger int
	for left < h.size {
		bigger = left
		if left + 1 < h.size && h.arr[left] < h.arr[left+1] {
			bigger = left + 1
		}
		if h.arr[bigger] < h.arr[index] {
			break
		}
		utility.Swap(h.arr, index, bigger)
		index = bigger
		left = (index<<1) + 1
	}
}